1. Field of the Invention
The invention relates to algebraic key establishment protocols for cryptographic applications.
2. Description of the Prior Art
The concepts, terminology and framework for understanding cryptographic key establishment protocols is given in Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, xe2x80x9cHandbook of Applied Cryptography,xe2x80x9d CRC Press (1997), pages 490-491.
A xe2x80x98protocolxe2x80x99 is a multi-party algorithm, defined by a sequence of steps specifying the actions required of two or more parties in order to achieve a specified objective.
A xe2x80x98key establishmentxe2x80x99 protocol is a protocol whereby a shared secret becomes available to two or more parties, for subsequent cryptographic applications.
A xe2x80x98key transportxe2x80x99 protocol is a key establishment protocol where one party creates or obtains a secret value, and securely transfers it to the other participating parties.
A xe2x80x98key agreementxe2x80x99 protocol is a key establishment protocol in which a shared secret is derived by two (or more) parties as a function of information contributed by, or associated with, each of the participating parties such that no party can predetermine the resulting value.
A xe2x80x98key-distributionxe2x80x99 protocol is a key establishment protocol whereby the established keys are completely determined a priori by initial keying material.
A xe2x80x98dynamicxe2x80x99 key establishment protocol is one whereby the key established by a fixed pair (or subset) of the participating parties varies on subsequent executions. Dynamic key establishment protocols are also referred to as xe2x80x98sessionxe2x80x99 key establishment protocols, and it is usually intended that these protocols are immune from known-key attacks.
The Diffie-Hellman key agreement protocol (also called xe2x80x98exponential key exchangexe2x80x99) is a fundamental algebraic protocol. It is presented in W. Diffie and M. E. Hellman, xe2x80x9cNew Directions in Cryptography,xe2x80x9d IEEE Transaction on Information Theory vol. IT 22 (November 1976), pp. 644-654. The Diffie-Hellman key agreement protocol provided the first practical solution to the key distribution problem, allowing two parties, never having met in advance or sharing keying material, to establish a shared secret by exchanging messages over an open channel. The security rests on the intractability of the Diffie-Hellman problem and the related problem of computing discrete logarithms in the multiplicative group of the finite field GF(p) where p is a large prime, cf. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, xe2x80x9cHandbook of Applied Cryptography,xe2x80x9d CRC Press (1997), page 113.
A key establishment protocol is said to have xe2x80x98perfect forward secrecyxe2x80x99 if compromise of long-term keys does not compromise past session keys. The idea of perfect forward security is that previous traffic is locked safely in the past. It may be provided by generating session keys by Diffie-Hellman key agreement, wherein the Diffie-Hellman exponentials are based on short term keys. If long-term secret keys are compromised, future sessions are nonetheless subject to impersonation by an active adversary (cf. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, xe2x80x9cHandbook of Applied Cryptography,xe2x80x9d CRC Press (1997), page 496).
xe2x80x98Point-to-point key updatexe2x80x99 techniques based on symmetric encryption would make use of a long-term symmetric key K shared a priori by two parties A and B. The Diffie-Hellman key agreement protocol allows for the establishment of such a K. Thus, the Diffie-Hellman key agreement protocol together with the symmetric encryption system provide the primitives in specifying a key transport protocol (cf. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, xe2x80x9cHandbook of Applied Cryptography,xe2x80x9d CRC Press (1997), page 497).
The definition of a monoid is given in Serge Lang, xe2x80x9cAlgebra,xe2x80x9d Third Edition, Addison-Wesley Publishing Company Inc. (1993), page 3.
Quote
Let S be a set. A mapping Sxc3x97Sxe2x86x92S is sometimes called a law of composition (of S into itself). If x, y are elements of S, the image of the pair (x, y) under the mapping is also called their product under the law of composition, and will be denoted xy . . . . Let S be a set with a law of composition. If x, y, z are elements of S, then we may form their product in two ways: (xy)z and x(yz). If (xy)z=x(yz) for all x, y, z in S then we say that the law of composition is associative.
An element e of S such that ex=x=xe for all x xcex5 S is called a unit element.
A unit element is unique, for if exe2x80x2 is another unit element, we have e=eexe2x80x2=exe2x80x2 by assumption. In most cases, the unit element is written simply 1 (instead of e) . . . .
A monoid is a set G, with a law of composition which is associative, and having a unit element (so that in particular, G is not empty).
Unquote
The definition of a group is given in Serge Lang, xe2x80x9cAlgebra,xe2x80x9d Third Edition, Addison-Wesley Publishing Company Inc. (1993), page 7.
Quote
A group G is a monoid, such that for every element x xcex5 G there exists an element y xcex5 G such that xy=yx=e. Such an element y is called an inverse for x. Such an inverse is unique. . . We denote this inverse by xxe2x88x921.
Unquote
The basic reference for concepts, terminology, and historical framework in combinatorial group theory is the monograph by Bruce Chandler and Wilhelm Magnus, xe2x80x9cThe history of combinatorial group theory: a case study in the history of ideas,xe2x80x9d Springer-Verlag (1982). We quote from page 3:
Quote
Combinatorial group theory may be characterized as the theory of groups which are given by generators and defining relations, or, as we would say today, by a presentation.
Unquote
The following problems were posed by M. Dehn in 1911. We quote from the monograph by Bruce Chandler and Wilhelm Magnus, xe2x80x9cThe history of combinatorial group theory: a case study in the history of ideas,xe2x80x9d Springer-Verlag (1982), page 19.
Quote
The Word Problem (called Identitaetsproblem by Dehn) Let an arbitrary element of the group be given through its buildup in terms of the generators. Find a method to decide in a finite number of steps whether this element equals the identity element or not.
The Conjugacy Problem (called Transformationsproblem by Dehn) Any two elements S and T of the group are given. Find a method to decide whether S and T are conjugate, i.e. whether there exists an element U of the group which satisfies the relation S=UTUxe2x88x921.
Unquote
The comparison form of the word problem can be stated as follows:
Comparison Form of the Word Problem Let u, v be any two elements of the group given. Find a method to decide in a finite number of steps whether u=v.
Assume that G is a group given by a presentation P(G). Let W(G) denote the set of all words in the generators and their inverses given in the presentation of G. The functional form of the word problem is to produce a mapping F from W(G) to W(G) such that for all u, v xcex5 W(G) it follows that F(u)=F(v) if and only if u, v define the same element of G with respect to the presentation P(G). For each element u xcex5 W(G) the element F(u) is termed the canonical form of u.
The functional form of the word problem requires an algorithm to produce canonical forms.
The Canonical Form Problem Let u be an arbitrary element of the given group. Specify a method to find, in a finite number of steps, a canonical form for u.
The functional form of the conjugacy problem requires, in addition, an algorithm to actually produce the conjugating element U.
Generalized Conjugacy Problem (functional form) Let S1, S2, . . . , Sn be elements of a group G. Assume that a xcex5G is secret and the set of n pairs of elements of the group G
{s1,axe2x88x921s1a},{s2,axe2x88x921s2a}, . . . {sn,axe2x88x921sna}
are publicly announced. Find an algorithm to actually produce such an element a.
It is self evident that this problem is harder than the original conjugacy problem. It has been known for some time that there exist groups with solvable word problem and unsolvable conjugacy problem. For example, in D. J. Collins and C. F. Miller III, xe2x80x9cThe conjugacy problem and subgroups of finite index,xe2x80x9d Proc. LMS Series 3, 34, (1977), p. 535-556) it is shown that there exist finitely presented groups G with solvable word problem which contain a subgroup H of index 2 with an unsolvable conjugacy problem. (Of course, the word problem for H is solvable.)
The discrete logarithm problem for a finite cyclic group of order p (a large prime) provides a bridge from combinatorial group theory to cryptographic protocols. A finite cyclic group of order p can be realized as the set of integers coprime to p modulo p, i.e., the finite set of integers {1, 2, . . . , pxe2x88x921} which forms a group under multiplication modulo p. Given fixed integers a, b xcex5{1, 2, . . . , pxe2x88x921}, where a is a primitive root modulo p, the discrete logarithm problem is to find an integer x (with 1xe2x89xa6xxe2x89xa6pxe2x88x921) such that
b=ax(mod p).
Another realization of a finite cyclic group of order p can be specified by a presentation with one generator a and one defining relation ap=1 where 1 denotes the identity element. Note that every element g of the group has a unique canonical form g=ax where x is an integer between one and p. It is clear that the discrete logarithm problem for a finite cyclic group of order p is thus identical to the canonical word problem for this group with respect to an arbitrary primitive element a.
The present invention employs the problems and algorithms of combinatorial group to create novel cryptographically secure algebraic key establishment protocols. More specifically, the cryptographic security of these protocols depend on the existence of groups with feasible word problem and hard conjugacy problem. Such an approach does not exist in the prior art.
It is the primary object of the present invention to provide novel cryptographically secure algebraic key establishment protocols based on a key establishment algebraic system KEAS.
Let (U, xcex8U) denote a monoid whose generating set {u1, u2, . . . } is enumerable and whose law of composition
xcex8UUxc3x97Uxe2x86x92U
is feasibly computable. Let (V, xcex8V) denote another such monoid. A KEAS is a five-tuple (U, V, xcex2, xcex31, xcex32) where
xcex2:Uxc3x97Uxe2x86x92V,xcex3i:Uxc3x97Vxe2x86x92V(i=1,2)
are feasibly computable functions satisfying the following properties.
(i) For all elements x, y1, y2xcex5U
xcex2(x,xcex8U(y1,y2))=xcex8V(xcex2(x,y1),xcex2(x,y2))
(ii) For all elements x, y xcex5 U
xcex31(x,xcex2(y,x))=xcex32(y,xcex2(x,y))
It is an object of the present invention to provide an apparatus which can perform monoid multiplication for KEAS.
It is an object of the present invention to provide a novel algebraic key agreement protocol based on KEAS=(U, V, xcex2, xcex31, xcex32) where U=V=G is a group.
It is an object and feature of the present invention to provide a cryptographically secure algebraic key agreement protocol whose security is based on the existence of groups whose word problem can be solved in polynomial time while no polynomial time algorithm to solve the generalized conjugacy problem is known.
It is an object and feature of the present invention to provide a cryptographically secure algebraic key agreement protocol which is based on the computation of a list of randomly rewritten conjugates in a group, thus reducing the steps and calculations in executing the protocol. This allows for easy implementation of the algorithms on low level computing devices with table driven modules.
It is an object of the present invention to provide an algebraic key agreement protocol based on KEAS=(U, V, xcex2, xcex31, xcex32) where U=V=G is the braid group.
It is an object of the present invention to provide an apparatus which randomly rewrites a word in the braid group in linear time in the word length.
A key transport protocol is an algorithm, initiated by an input, defined by a sequence of steps, which enables one party to securely transfer a key to another party. The key transport protocol is said to run in polynomial time if the number of steps required to transfer the key is a polynomial in the bit length of the input. If the polynomial is of the first degree, the key transport protocol is said to run in linear time.
It is an object and feature of the present invention to provide a cryptographically secure algebraic key transport protocol based on KEAS which allows for a linear time secure transfer of an encrypted key and requires polynomial time decryption of said encrypted key.
It is an object and feature of the present invention to provide a cryptographically secure algebraic key transport protocol based on KEAS=(U, V, xcex2, xcex31, xcex32) where U and V are monoids and U acts on a message space. The key transport protocol is a combination of the algebraic key agreement protocol based on KEAS, together with an apparatus which efficiently compares members of the message space. This allows for linear time secure transfer of an element of the message space and requires a polynomial time algorithm for comparison and retrieval of the message.
It is an object and feature of the present invention to provide a cryptographically secure algebraic key transport protocol based on KEAS=(U, V, xcex2, xcex31, xcex32) where the message space=U=V is the braid group which acts on itself by multiplication. This allows for the linear time secure transfer of an element of the message space (randomly rewritten word in the braid group) and requires a polynomial time algorithm to obtain a canonical form and decrypt the message.
It is an object and feature of the present invention to provide a cryptographically secure algebraic key transport protocol based on KEAS=(U, V, xcex2, xcex31, xcex32) where the message space=U=V is the braid group which acts on itself by conjugation. This allows for the linear time secure transfer of an element of the message space (randomly rewritten word in the braid group) and requires a polynomial time algorithm to obtain a canonical form and decrypt the message.
It is an object of the present invention to provide a cryptographically secure algebraic key transport protocol based on KEAS=(U, V, xcex2, xcex31, xcex32) where U=V is the braid group and the message space is a free group.
The system according to the invention is particularly suited towards implementation using currently available digital technology, commercially popular microprocessor based systems, and other affordable digital components. Significant portions of the system may be implemented and significant portions of the method according to the invention may be performed by software in a microcomputer based system. Moreover the system is quite suitable for implementation on emerging computer technologies, e.g., quantum computers.